package xiaohui

// 求无序数组排序后的相邻元素之间差的最大值
// 1 利用桶排序的思想，根据原始数组的长度n 创建n个桶，每一个桶代表一个区间范围
// 其中第1个桶从原始数组的最小值min开始，区间跨度是(max-min)/n-1
// 2 遍历原数组，把原数组每一个元素插入对应的桶中，记录每一个桶的最大值和最小值
// 3 遍历所有的桶，统计出每个桶的最大值，和这个桶右侧非空桶的最小值的差，数值最大的差就是原始数组排序后的相邻最大差

func GetMaxSortedDistance(numbs []int) int {
	// 1 计算 max min
	var max = numbs[0]
	var min = numbs[0]
	for i := 0; i < len(numbs); i++ {
		if numbs[i] > max {
			max = numbs[i]
		}
		if numbs[i] < min {
			min = numbs[i]
		}
	}

	var d = max - min
	// 如果max和min相等，说明数组数组所有元素都相等，返回
	if d == 0 {
		return 0
	}
	// 2 初始化桶
	var bucketNum = len(numbs)
	buckets := make([]Bucket, bucketNum)
	for i := 0; i < bucketNum; i++ {
		buckets[i] = Bucket{}
	}

	// 3 遍历原始数组，确定每个桶的最大最小值
	for i := 0; i < len(numbs); i++ {
		// 确定数组元素所归属的桶下标
		var index = (numbs[i] - min) * (bucketNum - 1) / d
		if buckets[index].min == 0 || buckets[index].min > numbs[i] {
			buckets[index].min = numbs[i]
		}
		if buckets[index].max == 0 || buckets[index].max < numbs[i] {
			buckets[index].max = numbs[i]
		}
	}
	// 4 遍历桶，找到最大差值
	var leftMax = buckets[0].max
	var maxDistance int
	for i := 0; i < len(buckets); i++ {
		if buckets[i].min == 0 {
			continue
		}
		if buckets[i].min-leftMax > maxDistance {
			maxDistance = buckets[i].min - leftMax
		}
		leftMax = buckets[i].max
	}
	return maxDistance
}

type Bucket struct {
	min int
	max int
}
